<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
                "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<head>
  <title>Description of dijkstra</title>
  <meta name="keywords" content="dijkstra">
  <meta name="description" content="Runs Dijkstra's shortest path algorithm on a distance matrix.">
  <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
  <meta name="generator" content="m2html &copy; 2003 Guillaume Flandin">
  <meta name="robots" content="index, follow">
  <link type="text/css" rel="stylesheet" href="../m2html.css">
</head>
<body>
<a name="_top"></a>
<!-- menu.html matlab -->
<h1>dijkstra
</h1>

<h2><a name="_name"></a>PURPOSE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2>
<div class="box"><strong>Runs Dijkstra's shortest path algorithm on a distance matrix.</strong></div>

<h2><a name="_synopsis"></a>SYNOPSIS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2>
<div class="box"><strong>function [D,P] = dijkstra( G, varargin ) </strong></div>

<h2><a name="_description"></a>DESCRIPTION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2>
<div class="fragment"><pre class="comment"> Runs Dijkstra's shortest path algorithm on a distance matrix.

 Runs Dijkstra's on the given SPARSE nxn distance matrix G, where missing
 values mean no edge (infinite distance). Uses a Finonacci heap resulting
 in fast computation. Finds the shortest path distance from every point
 S(i) in the 1xp source vector S to every other point j, resulting in a
 pxn distance matrix D. P(i,j) contains the second to last node on the
 path from S(i) to j. If point j is not reachable from point S(i) then
 D(i,j)=inf and P(i,j)=-1.

 USAGE
   [D P] = dijkstra( G, [S] )

 INPUT
   G   - sparse nxn distance matrix
   S   - 1xp array of source indices i

 OUPUT
   D   - pxn - shortest path lengths from S(i) to j
   P   - pxn - indicies of second to last node on path from S(i) to j

 EXAMPLE
  n=11; G=sparse(n,n); for i=1:n-1, G(i,i+1)=1; end; G=G+G';
  [D,P] = dijkstra(G,5), % D=[4:-1:0 1:6]; P=[2:5 -1 5:10];

 See also

 Piotr's Computer Vision Matlab Toolbox      Version 3.20
 Copyright 2014 Piotr Dollar.  [pdollar-at-gmail.com]
 Licensed under the Simplified BSD License [see external/bsd.txt]</pre></div>





<!-- Start of Google Analytics Code -->
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
var pageTracker = _gat._getTracker("UA-4884268-1");
pageTracker._initData();
pageTracker._trackPageview();
</script>
<!-- end of Google Analytics Code -->

<hr><address>Generated by <strong><a href="http://www.artefact.tk/software/matlab/m2html/" target="_parent">m2html</a></strong> &copy; 2003</address>
</body>
</html>
